import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//串联所有字母的子串
public class FindSubstring {
    public List<Integer> code(String s, String[] words) {
        Map<String, Integer> hash1 = new HashMap<>();
        List<Integer> ret = new ArrayList();

        for (String str: words){
            hash1.put(str, hash1.getOrDefault(str, 0) + 1);
        }

        int len = words[0].length();
        for (int i = 0; i < len; i++){
            Map<String, Integer> hash2 = new HashMap<>();
            for (int left = i, right = i, count = 0; right + len <= s.length(); right += len){
                //进窗口 + 维护count
                String in = s.substring(right, right + len);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                if (hash2.get(in) <= hash1.getOrDefault(in, 0)){
                    count++;
                }

                //出窗口
                if ((right - left + 1) > len *(words.length)){
                    String out = s.substring(left, left + len);
                    if (hash2.get(out) <= hash1.getOrDefault(out, 0)){
                        count--;
                    }
                    left += len;
                }

                if (count == words.length){
                    ret.add(left);
                }
            }
        }

        return ret;

    }

    public static void main(String[] args) {
        String s = "barfoothefoobarman";
        String[] words = new String[2];
        words[0] = "foo";
        words[1] = "bar";
        FindSubstring test = new FindSubstring();
        test.code(s, words);
    }
}
